In recent years, LDPC (Low Density Parity Check) codes, which have a high error-correcting capability, have been widely employed in transmission schemes including satellite digital broadcasting technologies, such as DVB (Digital Video Broadcasting)-S.2, which is used in Europe (see, for example, NPL 1). LDPC codes are also employed in next-generation terrestrial digital broadcasting technologies, such as DVB-T.2.
Recent studies have found that, like turbo codes, LDPC codes have a performance closer to the Shannon limit for larger code lengths. In addition, because of their characteristic of having minimum distances proportional to code lengths, LDPC codes have the feature of high block error probability performance, and have a further advantage in showing substantially no error floor phenomena, which is observed in the decoding characteristics of turbo codes and the like.
LDPC codes will now be described in more detail. LDPC codes are linear codes, and may or may not be binary. The following description will be given in the context of binary LDPC codes.
An LDPC code has the most striking feature that it is defined by a sparse parity check matrix. Here, the term “sparse matrix” refers to a matrix having a very small number of elements of 1 (or a matrix whose elements are almost zeros).
FIG. 1 illustrates an example of a parity check matrix H of an LDPC code.
In the parity check matrix H illustrated in FIG. 1, the weight of each column (column weight) (i.e., the number of 1s) is 3 and the weight of each row (row weight) is 6.
In an encoding operation using an LDPC code (LDPC encoding), for example, a generator matrix G is generated on the basis of a parity check matrix H. By multiplying the generator matrix G by binary information bits, a code word (i.e., an LDPC code) is generated.
Specifically, an encoding device that performs LDPC encoding first calculates a generator matrix G, where the equation GHT=0 is established between the transpose HT of the parity check matrix H and the generator matrix G. Here, if the generator matrix G is a K×N matrix, the encoding device multiplies the generator matrix G by a bit sequence (i.e., a vector u) of K information bits to generate a code word c (=uG) having N bits. The code word (or LDPC code) generated by the encoding device is received on the receiver side via a certain communication path.
An LDPC code can be decoded using the message passing algorithm, which is an algorithm called probabilistic decoding proposed by Gallager and which is based on belief propagation on a so-called Tanner graph with variable nodes (also referred to as “message nodes”) and check nodes. Here, the variable nodes and the check nodes will also be hereinafter referred to simply as “nodes” as appropriate.
FIG. 2 illustrates an LDPC code decoding procedure.
Note that, in the following description, a real-number value representing the likelihood of the value “0” of the i-th bit of an LDPC code (i.e., a code word) received on the receiver side, which is expressed in log likelihood ratio (i.e., a reception LLR), is also referred to as a “reception value u0i” as appropriate. Further, a message output from a check node is represented by uj, and a message output from a variable node is represented by vi.
In an LDPC code decoding process, first, as illustrated in FIG. 2, in step S11, an LDPC code is received, and a message (check node message) uj is initialized to “0”. In addition, a variable k of a counter for repetitive processing, which takes an integer value, is initialized to “0”. Then, the process proceeds to step S12. In step S12, a message (variable node message) vi is determined by performing computation given by Expression (1) (variable node computation) on the basis of a reception value u0i obtained through the reception of the LDPC code. A message uj is further determined by performing computation given by Expression (2) (check node computation) on the basis of the message vi.
                    [                  Math          .                                          ⁢          1                ]                                                                      v          i                =                              u                          0              ⁢                                                          ⁢              i                                +                                    ∑                              j                =                1                                                              d                  v                                -                1                                      ⁢                                                  ⁢                          u              j                                                          (        1        )                                [                  Math          .                                          ⁢          2                ]                                                                      tanh          ⁡                      (                                          u                j                            2                        )                          =                              ∏                          i              =              1                                                      d                c                            -              1                                ⁢                                          ⁢                      tanh            ⁡                          (                                                v                  i                                2                            )                                                          (        2        )            
Here, dv and dc in Expressions (1) and (2) are arbitrarily selectable parameters indicating the number of is in the vertical direction (columns) and the horizontal direction (rows) of the parity check matrix H, respectively. For example, for an LDPC code in a parity check matrix H with a column weight of 3 and a row weight of 6 (i.e., a (3,6) LDPC code) illustrated in FIG. 1, dv=3 and dc=6.
Note that, in each of the variable node computation of Expression (1) and the check node computation of Expression (2), a message input from an edge (or a line connecting between a variable node and a check node) from which a message is output is not the target of the computation. Thus, the range of computation is 1 to dv−1 or 1 to dc−1. Furthermore, the check node computation of Expression (2) is actually performed by creating in advance a table of a function R(v1, v2) given by Expression (3), which is defined by one output for two inputs v1 and v2, and sequentially (or recursively) using the table in the manner given by Expression (4).[Math. 3]x=2 tan h−1{tan h(v1/2)tan h(v2/2)}=R(v1,v2)  (3)[Math. 4]uj=R(v1,R(v2,R(v3, . . . R(vdc-2,vdc-1))))  (4)
In step S12, furthermore, the variable k is incremented by “1”. Then, the process proceeds to step S13. In step S13, it is determined whether the variable k is larger than a certain number of times of repetitive decoding C. If it is determined in step S13 that the variable k is not larger than C, the process returns to step S12, and subsequently, similar processing is repeatedly performed.
If it is determined in step S13 that the variable k is larger than C, the process proceeds to step S14. In step S14, a message vi as a final output result of decoding is determined by performing computation given by Expression (5), and is output. Then, the LDPC code decoding process ends.
                    [                  Math          .                                          ⁢          5                ]                                                                      v          i                =                              u                          0              ⁢                                                          ⁢              i                                +                                    ∑                              j                =                1                                            d                v                                      ⁢                                                  ⁢                          u              j                                                          (        5        )            
Here, the computation of Expression (5) is performed using, unlike the variable node computation of Expression (1), the messages uj from all the edges connected to a variable node.
FIG. 3 illustrates an example of a parity check matrix H of a (3,6) LDPC code (with a code rate of 1/2 and a code length of 12).
In the parity check matrix H illustrated in FIG. 3, similarly to FIG. 1, the column weight is 3 and the row weight is 6.
FIG. 4 illustrates a Tanner graph of the parity check matrix H illustrated in FIG. 3.
Here, in FIG. 4, a check node is represented by a plus “+” sign, and a variable node is represented by an equal “=” sign. A check node and a variable node correspond to each row and column of the parity check matrix H, respectively. A connection between a check node and a variable node is an edge, and corresponds to an element of “1” in the parity check matrix.
More specifically, in a case where the element in the j-th row and the i-th column of the parity check matrix is 1, in FIG. 4, the i-th variable node (“=” node) from the top and the j-th check node (“+” node) from the top are connected by an edge. An edge indicates that a code bit corresponding to a variable node has a constraint corresponding to a check node.
In the sum product algorithm, which is an LDPC code decoding method, variable node computation and check node computation are repeatedly performed.
FIG. 5 illustrates variable node computation to be performed at a variable node.
At a variable node, a message vi corresponding to an edge for which calculation is to be performed is determined through the variable node computation of Expression (1) using messages u1 and u2 from the remaining edges connected to the variable node and also using a reception value u0i. The messages corresponding to the other edges are also determined in a similar way.
FIG. 6 illustrates check node computation to be performed at a check node.
Here, the check node computation of Expression (2) can be rewritten as Expression (6) by using the relationship of the equation a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b), where sign(x) is 1 for x≥0 and −1 for x<0.
                    [                  Math          .                                          ⁢          6                ]                                                                                                                u                j                            =                            ⁢                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        ⁡                                      (                                                                  ∏                                                  i                          =                          1                                                                                                      d                            c                                                    -                          1                                                                    ⁢                                                                                          ⁢                                              tanh                        ⁡                                                  (                                                                                    v                              i                                                        2                                                    )                                                                                      )                                                                                                                          =                            ⁢                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                                              ∑                                                          i                              =                              1                                                                                                                      d                                c                                                            -                              1                                                                                ⁢                                                                                                          ⁢                                                      ln                            ⁡                                                          (                                                                                                                                tanh                                  ⁡                                                                      (                                                                                                                  v                                        i                                                                            2                                                                        )                                                                                                                                                              )                                                                                                      }                                            ×                                                                        ∏                                                      i                            =                            1                                                                                                              d                              c                                                        -                            1                                                                          ⁢                                                                                                  ⁢                                                  sign                          ⁡                                                      (                                                          tanh                              ⁡                                                              (                                                                                                      v                                    i                                                                    2                                                                )                                                                                      )                                                                                                                ]                                                                                                                          =                            ⁢                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                  -                                                      (                                                                                          ∑                                                                  i                                  =                                  1                                                                                                                                      d                                    c                                                                    -                                  1                                                                                            ⁢                                                                                                                          ⁢                                                              -                                                                  ln                                  ⁡                                                                      (                                                                          tanh                                      ⁡                                                                              (                                                                                                                                                                                                                        v                                              i                                                                                                                                                                            2                                                                                )                                                                                                              )                                                                                                                                                        )                                                                          }                                                              ]                                                  ×                                                      ∏                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                                                          ⁢                                      sign                    ⁡                                          (                                              v                        i                                            )                                                                                                                              (        6        )            
If the function ϕ(x) is defined as the equation ϕ(x)=ln(tan h(x/2)) for x≥0, the equation ϕ−1(x)=2 tan h−1(e−x) is established. Thus, Expression (6) can be transformed into Expression (7).
                    [                  Math          .                                          ⁢          7                ]                                                                      u          j                =                                            ϕ                              -                1                                      ⁡                          (                                                ∑                                      i                    =                    1                                                                              d                      c                                        -                    1                                                  ⁢                                                                  ⁢                                  ϕ                  ⁡                                      (                                                                                        v                        i                                                                                    )                                                              )                                ×                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                                                  ⁢                          sign              ⁡                              (                                  v                  i                                )                                                                        (        7        )            
At a check node, the check node computation of Expression (2) is performed in accordance with Expression (7).
More specifically, at a check node, as illustrated in FIG. 6, a message uj corresponding to an edge for which calculation is to be performed is determined through the check node computation of Expression (7) using messages v1, v2, v3, v4, and v5 from the remaining edges connected to the check node. The messages corresponding to the other edges are also determined in a similar way.
Note that the function ϕ(x) in Expression (7) can be represented by the equation ϕ(x)=ln((ex+1)/(ex−1)), where ϕ(x)=ϕ−1(x) for x>0. The functions ϕ(x) and ϕ−1(x) may be implemented in hardware by using an LUT (Look Up Table), where the same LUT is used for both functions.